The problem can be found at the following link: Question Link
An observation based question, when you try few examples you get a sequence formula.
- To determine if a number is lucky, I start with a counter
cnt
set to 2. - I then enter a loop that continues until
cnt
is less than or equal ton
.- Inside the loop, I check if
n
is divisible bycnt
. If it is, I returnfalse
because a lucky number cannot have any divisors other than 1. - If
n
is not divisible bycnt
, I subtractn
divided bycnt
fromn
and incrementcnt
by 1.
- Inside the loop, I check if
- After the loop, if we haven't returned
false
, I returntrue
because the number is a lucky number.
- Time Complexity: The time complexity of this algorithm is
O(sqrt(n))
, where n is the input number. - Auxiliary Space Complexity: The algorithm uses a constant amount of extra space, so the auxiliary space complexity is O(1).
class Solution {
public:
bool isLucky(int n) {
int cnt = 2;
while(cnt <= n){
if(n % cnt == 0)
return false;
n -= n/cnt;
++cnt;
}
return true;
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star
to the getlost01/gfg-potd repository.